public class CanCompleteCircuit {

    public int canCompleteCircuit1(int[] gas, int[] cost) {
        int n = gas.length;
        int[] temp = new int[n];
        int index = -1;
        boolean flag = false;
        for (int i = 0; i < n; i++) {
            temp[i] = gas[i] - cost[i];
            if (index == -1 && temp[i] > 0) index = i;
            if (temp[i] < 0) flag = true;
        }
        if (flag && index == -1) return -1;
        if (index == -1) return 0;
        int i = index;
        while (i % n < index || i < n) {
            int sum = 0;
            if (temp[i % n] > 0) {
                int j = i;
                while (sum >= 0 && (i % n < j || i < n)) {
                    sum += temp[i % n];
                    ++i;
                }
                if (sum >= 0) return j;
            } else ++i;
        }
        return -1;
    }

    public int canCompleteCircuit(int[] gas, int[] cost) {
        int start = 0;
        int sum = 0;
        int temp = 0;
        for (int i = 0; i < gas.length; i++) {
            temp += gas[i] - cost[i];
            sum += gas[i] - cost[i];
            if (temp < 0) {
                start = i + 1;
                temp = 0;
            }
        }
        return sum < 0 ? -1 : start;
    }
}